{\magonebf 3.9 Integer Sets  (int\_set)}

An instance $S$ of the data type $int\_set$ is a subset of a fixed interval 
interval $[a..b]$ of the integers.

\def\name{$int\_set$}
\def\type{int\_set}

\bigskip
{\bf 1. Creation of an int\_set}

\create S (a,b)

creates an instance \var\ of type $int\_set$ for elements from $[a..b]$ and 
initializes it to the empty set. 

\bigskip
{\bf 2. \operations}
\+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
\+\op void insert  {int\ x} 
                            {adds $x$ to \var}
\+\nop                      {\precond $a\le x\le b$.}
\smallskip
\+\op void del     {int\ x} 
                            {deletes $x$ from \var}
\+\nop                      {\precond $a\le x\le b$.}
\smallskip
\+\op bool member  {int\ x} 
                            {returns true if $x$ in \var, false otherwise}
\+\nop                      {\precond $a\le x\le b$.}
\smallskip
\+\op void clear   {}    
                            {makes \var\ the empty set}
\bigskip
\+&$int\_set$  &$S1\ =\ S2$   &assignment\cr
\smallskip
\+&$int\_set$  &$S1\ |\ S2$   &returns the union of $S1$ and $S2$\cr
\smallskip
\+&$int\_set$  &$S1\ \&\ S2$  &returns the intersection of $S1$ and $S2$\cr
\smallskip
\+&$int\_set$  &$\tilde{}\ S$ &returns the complement of $S$\cr
\smallskip


\bigskip
{\bf 3. Implementation}

Integer sets are implemented by bit vectors. Operations insert, delete,
member,empty, and size take constant time. Clear, intersection, union 
and complement take time $O(b-a+1)$.

